A network of computing devices often includes at least one computing device that functions as a “router,” directing message traffic on the network. Traditionally, routers connect two or more sub-networks such that messages between computing devices on different sub-networks are directed to the appropriate sub-network for delivery to their targeted destination. At the center of a router's functionality is a “routing table” that correlates identifiers of individual computing devices to network paths that can be used to reach that computer. Routing tables can be implemented in a variety of ways, and are not limited to traditional look-up tables. Indeed, while a traditional look-up table can be suitable for implementing routing tables for networks comprising a limited number of computing devices, router tables for large networks, such as the ubiquitous Internet, that comprise millions of individual computing devices can instead be implemented in uniquely structured forms designed for highly efficient information retrieval.
The information contained within a routing table can likewise vary depending on the type of routing used. For example, in a simple routing scheme known as “hop-by-hop routing”, the routing table can correlate identifiers of individual computing devices to the address of the next device along the path to that destination; in other words, the next “hop.” Alternatively, more complex routing schemes are based on knowledge of network topology and, consequently, a routing table in such a scheme can correlate identifiers of individual computing devices to one or more paths to that computing device.
Because a router can comprise information critical to inter-network communication, it can easily become a bottleneck for network communication. For example, if a router becomes clogged or non-responsive, it can slow down, or even interrupt, various network communications. To eliminate such a bottleneck, distributed routing tables (DRTs) can be used, whereby multiple computing devices can each host some or all of a routing table that can be used in a distributed fashion. For example, each one of multiple computing devices can host a portion of a DRT that comprises information regarding a subset of computing devices on the network. Thus, for each message received by a computing device that is not destined for that device, the computing device can reference its portion of the DRT and identify another computing device that may be more likely to be able to ultimately deliver that message to its intended recipient. Unlike a centralized router, which can no longer direct messages to their intended destination when it fails, a DRT can continue to direct messages even if one or more computing devices fail. In such a failure scenario, the remaining, operational, computing devices simply direct messages to other, still operational, computing devices, and thereby ultimately deliver messages to their intended destinations.